/*
    4. Write a C program to sort a list of elements using the insertion sort algorithm. 
    Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) 
    one item at a time. It is much less efficient on large lists than other algorithms such as
    quicksort, heapsort, or merge sort.
*/

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void insertsort(int a[], int len)
{
    int i,j;
    for(i = 0; i < len - 1; i++){
        for(j = i; j >= 0; j--){
            if(a[j] > a[j + 1]){
                swap(&a[j], &a[j + 1]);
            }
        }
    }
}

int main(void)
{
    int alen;
    int *a;
    int i;
    printf("Input the size of array : ");
    scanf("%d", &alen);
    a = (int *)malloc(alen * sizeof(int));
    for(i = 0; i < alen; i++){
        scanf("%d", &a[i]);
    }
    insertsort(a, alen);
    printf("After insertion sort : \n");
    for(i = 0; i < alen; i++){
        printf("%d, ", a[i]);
    }

    return 0;
}